package year2023.recursion;

/*
字符串全排列

编写一个方法，确定某字符串的所有排列组合。

给定一个string A和一个int n,代表字符串和其长度，请返回所有该字符串字符的排列，保证字符串长度小于等于11且字符串中字符均为大写英文字符，排列中的字符串按字典序从大到小排序。(不合并重复字符串)

测试样例：
"ABC"
返回：
["CBA","CAB","BCA","BAC","ACB","ABC"]
 */


import java.util.ArrayList;
import java.util.Arrays;

public class Code06_Permutations {

    public static void main(String[] args) {
        ArrayList<String> res = new Code06_Permutations().getPermutation("abc");
        System.out.println(res.size());
        System.out.println(res);
    }

    //迭代
    public ArrayList<String> getPermutation1(String A){
        int n = A.length();
        ArrayList<String> res = new ArrayList<>();
        res.add(A.charAt(0)+"");//初始化，包含第一个字符
        for (int i = 1; i < n; i++) {//第二个字符插入到钱穆按生成集合的每个元素里面
            ArrayList<String> res_new = new ArrayList<>();
            char c = A.charAt(i);//新字符
            for (String str : res) {//访问上一趟集合中的每个字符串
                //插入到每个位置，形成一个新串
                String newStr = c + str;//加在前面
                res_new.add(newStr);
                newStr = str + c;//加在后面
                res_new.add(newStr);

                for (int j = 1; j < str.length(); j++){
                    newStr = str.substring(0,j) + c + str.substring(j);
                    res_new.add(newStr);
                }
            }
            res = res_new;
        }
        return res;
    }

    //back tracking回溯

    ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> getPermutation(String A){
        char[] arr = A.toCharArray();
        Arrays.sort(arr);//排序
        getPermutationCore(arr, 0);
        return res;
    }

    private void getPermutationCore(char[] arr, int k){
        if (k == arr.length){//排好了一种情况，递归的支路走到底了
            res.add(new String(arr));
        }

        //从k位开始的每个字符，都尝试放在新排列的k这个位置
        for (int i = k; i < arr.length; i++) {
            swap(arr, k, i);//把后面每个字符换到k位
            getPermutationCore(arr, k + 1);
            swap(arr, k, i);//回溯
        }
    }

    static void swap(char[] arr, int i, int j){
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }



}
